﻿#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdlib>
#include<ctime>
#include<cassert>
using namespace std;
enum Color{
	Red,
	Black
};

template<class T>
class RBTreeNode {
public:
	RBTreeNode<T>* _pParent;
	RBTreeNode<T>* _pLeft;
	RBTreeNode<T>* _pRight;
	T _data;
	Color _color;

	RBTreeNode()
		:_pParent(this)
		,_pLeft(this)
		,_pRight(this){}
		
	RBTreeNode(const T& data)
		:_pParent(nullptr)
		, _pLeft(nullptr)
		, _pRight(nullptr)
		, _data(data) 
		, _color(Red){}
};

template< class T>
class RBTree
{
	typedef RBTreeNode<T> Node;
public:
	RBTree():_pHead(new Node){}

//父节点‌：哨兵节点的父节点指向根节点。
//‌左右子节点‌：哨兵节点的左子节点指向树中的最小值节点，
//	        右子节点指向树中的最大值节点。
//这种设计的主要目的是简化遍历操作，确保根节点始终存在，
//从而避免在遍历过程中处理空指针的情况‌

//‌简化遍历操作‌：由于哨兵节点的存在，遍历操作可以更简洁地处理，不需要单独处理根节点的情况。
//‌确保根节点存在‌：即使在树为空的情况下，哨兵节点也能确保根节点的存在，从而避免空指针异常。

	// 注意：为了简单起见，本次实现红黑树不存储重复性元素
	bool Insert(const T& data) {
		if (_pHead->_pParent == _pHead) {
			Node* newone = new Node(data);
			newone->_color = Black;
			newone->_pParent = _pHead;
			_pHead->_pParent = newone;
			_pHead->_pLeft = newone;
			_pHead->_pRight = newone;
			return true;
		}

		Node* cur = GetRoot();
		Node* parent = GetRoot();
		int LeftFlag = 1;
		int RightFlag = 1;
		while (cur) {
			if (cur->_data < data) {
				parent = cur;
				cur = cur->_pRight;
				LeftFlag = 0;
			}
			else if (cur->_data > data) {
				parent = cur;
				cur = cur->_pLeft;
				RightFlag = 0;
			}
			else {
				return false;
			}
		}

		cur = new Node(data);
		if (parent->_data < data) {
			parent->_pRight = cur;
		}
		else {
			parent->_pLeft = cur;
		}
		cur->_pParent = parent;
		if (LeftFlag) {
			_pHead->_pLeft = cur;
		}
		else if (RightFlag) {
			_pHead->_pRight = cur;
		}

		//cout << "插入 ";
		//this->Printf();
		//旋转并不改变谁是最大值谁是最小值
		while (parent&&parent!=_pHead&&parent->_color==Red) {
			Node* grandp = parent->_pParent;
			if (grandp->_pLeft == parent) {
				Node* uncle = grandp->_pRight;

				if (uncle && uncle->_color == Red) {
					parent->_color = uncle->_color = Black;
					grandp->_color = Red;

					cur = grandp;
					parent = cur->_pParent;
				}
				else {
					if (parent->_pLeft == cur) {
						RotateR(grandp);
						parent->_color = Black;
						grandp->_color = Red;
					}
					else {
						//g
						//p u
						// c

						//g
						//c u
						//p
					
						//c
						//p g
						//   u
						RotateL(parent);
						RotateR(grandp);
						cur->_color = Black;
						grandp->_color = Red;
					}
					break;
				}
			}
			else {
				Node* uncle = grandp->_pLeft;

				if (uncle && uncle->_color == Red) {
					parent->_color = uncle->_color = Black;
					grandp->_color = Red;

					cur = grandp;
					parent = cur->_pParent;
				}
				else {
					if (parent->_pRight == cur) {
						RotateL(grandp);
						parent->_color = Black;
						grandp->_color = Red;
					}
					else {
						RotateR(parent);
						RotateL(grandp);
						cur->_color = Black;
						grandp->_color = Red;
					}
					break;
				}

			}
		}
		_pHead->_pParent->_color = Black;
		return true;
	}

	// 检测红黑树中是否存在值为data的节点，存在返回该节点的地址，否则返回nullptr
	Node* Find(const T& data) {
		if (_pHead->_pParent == _pHead) {
			return false;
		}

		Node* cur = GetRoot();
		while (cur) {
			if (cur->_data < data) {
				cur = cur->_pRight;
			}
			else if (cur->_data > data) {
				cur = cur->_pLeft;
			}
			else {
				return cur;
			}
		}

		return nullptr;
	}

	// 获取红黑树最左侧节点
	Node* LeftMost() {
		return _pHead->_pLeft;
	}

	// 获取红黑树最右侧节点
	Node* RightMost() {
		return _pHead->_pRight;
	}

	void Printf() {
		cout << "根节点(" << GetRoot()->_data << ")" << " ";
		printf(GetRoot());
		cout << endl;
	}

	// 检测红黑树是否为有效的红黑树，注意：其内部主要依靠_IsValidRBTRee函数检测
	bool IsValidRBTRee() {
		return _IsValidRBTRee(_pHead);
	}
	bool _IsValidRBTRee(Node* pRoot) {
		if (pRoot->_pParent == pRoot) {
			return true;
		}

		if (GetRoot()->_color != Black) {
			cout << GetRoot()->_data << "根节点不为黑";
		}

		//遍历最方便的一条路径计算黑色节点
		int pathBlack = 0;
		Node* cur = GetRoot();
		while (cur){
			if (cur->_color == Black) {
				++pathBlack;
			}
			cur = cur->_pLeft;
		}
		return _IsValidRBTRee(GetRoot(), 0, pathBlack);
	}
private:
	void printf(Node* root) {
		if (!root) {
			return;
		}
		printf(root->_pLeft);
		cout << root->_data <<"("<<root->_color<<")" << " ";
		printf(root->_pRight);
	}
	bool _IsValidRBTRee(Node* pRoot, size_t blackCount, size_t pathBlack) {
		if (!pRoot) {
			if (blackCount != pathBlack) {
				cout << "blackCount:" << blackCount << " pathBlack:" << pathBlack << endl;
				cout << "路径黑节点数量不同" << endl;
				return false;
			}
			return true;
		}

		if (pRoot->_color == Red && pRoot->_pParent->_color == Red) {
			cout << "出现相连的红色节点" << endl;
			return false;
		}
		else if (pRoot->_color == Black){
			++blackCount;
		}

		return _IsValidRBTRee(pRoot->_pLeft, blackCount, pathBlack) &&
			_IsValidRBTRee(pRoot->_pRight, blackCount, pathBlack);

	}
	// 左单旋
	//g
	//p u
	// c
	//
	//g
	//c u
	//p
	void RotateL(Node* pParent) {
		Node* curR = pParent->_pRight;
		Node* curRL = curR->_pLeft;
		Node* grandpa = pParent->_pParent;

		curR->_pParent = grandpa;
		if (pParent == GetRoot()) {
			grandpa->_pParent = curR;
		}
		else {
			if (grandpa->_data < curR->_data)
				grandpa->_pRight = curR;
			else
				grandpa->_pLeft = curR;
		}

		pParent->_pRight = curRL;
		if (curRL) {
			curRL->_pParent = pParent;
		}

		pParent->_pParent = curR;
		curR->_pLeft = pParent;
	}
	// 右单旋
	void RotateR(Node* pParent) {
		Node* curL = pParent->_pLeft;
		Node* curLR = curL->_pRight;
		Node* grandpa = pParent->_pParent;

		curL->_pParent = grandpa;
		if (pParent == GetRoot()) {
			grandpa->_pParent = curL;
		}
		else {
			if (grandpa->_data < curL->_data)
				grandpa->_pRight = curL;
			else
				grandpa->_pLeft = curL;
		}

		pParent->_pLeft = curLR;
		if (curLR) {
			curLR->_pParent = pParent;
		}

		pParent->_pParent = curL;
		curL->_pRight = pParent;
	}
	// 为了操作树简单起见：获取根节点
	Node*& GetRoot() {
		return _pHead->_pParent;
	}
private:
	Node* _pHead;
};
void test1() {
	RBTree<int> tree;

	// 测试插入有序数据
	for (int i = 1; i <= 10; ++i) {
		tree.Insert(i);
	}
	tree.IsValidRBTRee();
}

void test2() {
	RBTree<int> tree;
	// 测试插入随机数据
	srand(time(0));
	size_t begin = clock();
	for (int i = 0; i < 10000; i++) {
		tree.Insert(rand());
	}
	size_t end=clock();

	tree.IsValidRBTRee();
	tree.Printf();
	cout << "min:" << tree.LeftMost()->_data<<" "
		<< "max:" << tree.RightMost()->_data << endl;
	cout << "用时:" << end - begin;
}
int main() {
	test2();
	return 0;
}